package jiaoheng;

import org.junit.Test;
public class 排序2{
    @Test
    public void bubbleSort(){
        int[] arr = {3,1,4,6,5};
        for(int i=0;i<arr.length-1;i++){
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int tmp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
        }
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }
    @Test
    public void selectSort(){
        int[] arr = {3,1,4,6,5};
        for(int i=0;i<arr.length-1;i++){
            int minPosition=i;
            for(int j=i;j<arr.length-1;j++){
                if(arr[minPosition]>arr[j+1]){
                    minPosition=j+1;
                }
            }
            if(minPosition!=i){
                int tmp=arr[minPosition];
                arr[minPosition]=arr[i];
                arr[i]=tmp;
            }
        }
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }
    @Test
    public void insertSort(){
        int[] arr = {3,1,4,6,5};
        for(int i=1;i<arr.length;i++){//要插入元素位置i
            int insertValue = arr[i];
            // 最终要挪动到的位置j
            int j;
            for(j=i-1;j>=0;j--){//
                if(arr[j]>insertValue){
                    arr[j+1]=arr[j];//挪动数字
                }else{
                    break;
                }
            }
            j++; //这个j++表示实际要插入的位置
            arr[j]=insertValue;
        }
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }
    /*

     */
    @Test
    public void shellSort(){
        int[] arr = {3,1,4,6,5};
        for(int gap = arr.length/2;gap>0;gap/=2){ // logN
            // 这里从分组的后面那个数开始
            for(int i=gap;i<arr.length;i++){
                int insertValue=arr[i];
                int j;
                for(j=i-gap;j>=0;j-=gap){
                    if(arr[j]>insertValue){
                        arr[j+gap]=arr[j];
                    }else{
                        break;
                    }
                }
                j+=gap;
                arr[j]=insertValue;
            }
        }
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }

}
